//expand.cpp - expand a buffer, given variable values
//TODO: add proper quoting support for prefix and body scanning.
#include "precompiled.hpp"
#include "expand.hpp"
#include "exec_context.hpp"
#include "jam_lists.hpp"
#include "detail/stack_allocator.hpp"
#include <boost/array.hpp>

#define MAX_EMBEDDED_VARS 100

//Structure with the part of variable name. 
struct var_piece
{
	var_piece() : is_sublist_(true), is_modifier_(false) {}

	var_piece(const jam_string& str, bool is_modifier) : 
		is_sublist_(false), value_(str), is_modifier_(is_modifier) {}	

	//This value is set to 'true' if this piece is a list of values
	bool is_sublist_; 
	//This value is set to 'true' if this piece is a starting symbol of a modifier
	bool is_modifier_;
	//This string is used to accumulate data.
	jam_string value_;
	//This list contains the list of values. 'can_have_mods_' must be 'false' for
	//this value to be valid
	jam_list val_list_;
};
typedef fixed_size_list<var_piece,MAX_EMBEDDED_VARS> piece_list_t;

//Structure for iteration over variable pieces
struct piece_iteration_entry
{
	piece_iteration_entry() : entry(), is_sublist_(), is_modifier_() {}

	bool is_sublist_,is_modifier_;
	const char* entry;
	jam_list::const_iterator pos,begin,end;
};

void expand_var_name(const list_of_lists &func_args,
	const jam_module &context, const jam_string &name, jam_list &res)
{
	assert(name.size()>=4 && name[0]=='$' && name[1]=='(' && 
		name[name.size()-1]==')');

	const jam_list *var_val=NULL; //Performance optimization

	if (name.size()==4)
	{
		//$(x)
		char third_char=name[2];
		if (third_char=='<')
			var_val=&get_list_element(func_args,0);
		else if (third_char=='>')
			var_val=&get_list_element(func_args,1);
		else if (jam_is_digit(third_char)) //Try $(n) vars
		{
			int digit=digit_to_num(third_char);			
			if (digit==0)
			{
				res=null_list;
				return;
			}
			var_val=&get_list_element(func_args,digit-1);
		}
	}
	if (!var_val)
	{
		//Check the global hash map.
		jam_string bare_name=name.ref_substr(2,name.size()-3);
		//jam_string(boost::cref(name.data()+2),name.size()-3);
		var_val=&context.get_var_value(bare_name);
	}

	//Skip over empty embedded variable values. TODO: is this OK?
	if (var_val->empty())
		return;
	
	if (var_val->size_is_one())
	{
		const jam_string &ref=var_val->front();
		if (scan_for_var(ref.begin(),ref.end())==ref.end())
		{
			res.push_back(var_val->front());
			return;
		}
	}

	//Clever, clever, clever hack :)
	if (var_val->cache_valid_ && !var_val->cached_need_recursive_expansion_ && 
		res.empty())
	{
		res=*var_val;
		return;
	}

	//The returned list may contain another variables, so perform embedded expansion
	res.hint_list_size(*var_val);
	bool needs_recursive_expand=false;
	for(jam_list::const_iterator n=var_val->begin(),nend=var_val->end();n!=nend;++n)
	{
		if (scan_for_var(n->begin(),n->end())!=n->end())
		{
			expand_string(func_args,context,*n,res,1); //TODO: fix level
			needs_recursive_expand=true;
		}
		else
			res.push_back(*n); //Fast-track to trivial expansion
	}
	boost::get(var_val->cache_valid_)=true;
	boost::get(var_val->cached_need_recursive_expansion_)=needs_recursive_expand;
}

typedef std::pair<int,std::string::const_iterator> number_pair_t;
number_pair_t parse_num(const std::string::const_iterator &begin,
	const std::string::const_iterator &end)
{
	assert(begin!=end);

	std::string::const_iterator cur=begin;
	if (*cur=='-') cur++;
	while(cur!=end) if (!jam_is_digit(*cur)) break; else cur++;

	return std::make_pair(atoi(&*begin),cur);
}

void process_subscript(const std::string &str,jam_list &tmp)
{
	//TODO: add subscript processing
	number_pair_t first(parse_num(str.begin(),str.end()));
	if (first.first==0) throw jam_exception("Wrong index!");

	if (first.second!=str.end())
	{
		number_pair_t last(-1,str.end());
		//Still some stuff		
	} else
	{
		//Return a single element
		jam_list new_list;		
		size_t dist=abs(first.first)-1;
		if (dist>=tmp.size()) throw jam_exception("Subscript out of range: "+str.c_str());
		if (first.first>0)
		{
			jam_list::const_iterator f=tmp.begin();
			std::advance(f,dist);
			new_list.push_back(*f);
		} else
		{
			jam_list::const_reverse_iterator f=tmp.rbegin();
			std::advance(f,dist);
			new_list.push_back(*f);
		}
	}
}

void process_mods(const std::string &str,jam_list &tmp)
{
	//TODO: add modifiers processing

}

//This function receives the list of possible variable names (in the form of
//'name pieces'). This function appends the result of variable expansions as 
//a result in 'res' parameter.
void expand_var(const list_of_lists &func_args, const jam_module &context, 
	const piece_list_t &pieces, size_t last_name_piece, jam_list &res)
{
	if (pieces.size()==1 && !pieces[0].is_sublist_) //Fast-track to trivial expansion
	{
		//Expand the variable		
		expand_var_name(func_args,context,pieces.front().value_,res);
		return;
	}
	
	//Create a list of iterators.
	boost::array<piece_iteration_entry,MAX_EMBEDDED_VARS> iter;
	size_t cur_pos=0;
	for(size_t f=0,fend=pieces.size();f!=fend;++f)
	{
		const var_piece &piece=pieces[f];
		piece_iteration_entry &ent=iter[cur_pos++];
		ent.is_sublist_=piece.is_sublist_;
		ent.is_modifier_=piece.is_modifier_;
		if (!piece.is_sublist_) //A plain piece
			ent.entry=piece.value_.c_str();
		else
		{
			ent.begin=piece.val_list_.begin();
			ent.end=piece.val_list_.end();
			ent.pos=ent.begin;
		}
	}
			
	boost::array<size_t,MAX_EMBEDDED_VARS> piece_pos_list;
	std::string cur_var_name;
	size_t cur_var_name_valid_to=0;

	if (last_name_piece==0) last_name_piece=pieces.size();
	//Variable expansion code needs variables in $(varname) format,
	//but if there are modifiers present (like $(varname:U) ) then
	//piece iteration code will not add the final brace.
	//Besides, this also works as a 'have modifiers' flag.
	bool need_to_add_the_final_brace=pieces.size()!=last_name_piece;

	//Iterate over the variable pieces
	while(true)
	{
		//Create variable name from pieces
		for(size_t f=cur_var_name_valid_to;f<last_name_piece;++f)
		{
			piece_pos_list[f]=cur_var_name.size();

			if (!iter[f].is_sublist_)
				cur_var_name+=iter[f].entry;
			else
				cur_var_name+=(iter[f].pos)->c_str();
			cur_var_name_valid_to=f;
		}

		//Expand the variable
		//This will skip over empty embedded variable values. TODO: is this OK?
		if (!need_to_add_the_final_brace)
			expand_var_name(func_args,context,
				jam_string(boost::cref(cur_var_name.c_str()),cur_var_name.size()),res);
		else //That means there's some modifiers
		{			
			jam_list tmp; //Collect results to a temporary list
			cur_var_name+=')';
			expand_var_name(func_args,context,
				jam_string(boost::cref(cur_var_name.c_str()),cur_var_name.size()),tmp);

			//Don't forget the final brace! It has a separate piece which we don't need
			size_t start_name_size=cur_var_name.size()-1;
			std::string cur_mods;
			bool colon_found=false;
			bool collecting_string=false;
			bool collecting_subscript=false;

			for(size_t f=last_name_piece,fend=pieces.size();f<fend;++f)
			{
				piece_pos_list[f]=cur_mods.size()+start_name_size;

				if (!iter[f].is_sublist_)
				{					
					//This is a control symbol ('[',']',':',')') or just a simple string.

					if (!colon_found && strcmp(iter[f].entry,"[")==0)
					{
						//Process starting '[' of a subscript.
						assert(cur_mods.empty());
						if (colon_found)
							throw jam_exception(
							"Malformed variable expansion: subscript after modifier!");
						collecting_subscript=collecting_string=true;
					} else if (!colon_found && strcmp(iter[f].entry,"]")==0)
					{
						//Process closing ']' of a subscript.
						if (!collecting_subscript)
							throw jam_exception(
							"Malformed variable expansion: unballanced ']'!");
						if (cur_mods.empty())
							throw jam_exception(
							"Malformed variable expansion: empty subscript!");
						process_subscript(cur_mods,tmp);
						cur_mods.clear();
						collecting_string=collecting_subscript=false;
					} else if (strcmp(iter[f].entry,":")==0)
					{
						assert(!collecting_subscript);
						if (collecting_string)
						{
							//We've already collected a modifier
							process_mods(cur_mods,tmp);
							cur_mods.clear();
						} else
							assert(cur_mods.empty());

						//Start collecting modifiers
						collecting_string=colon_found=true;
					} else if (strcmp(iter[f].entry,")")==0)
					{
						if (collecting_subscript)
							throw jam_exception("Malformed variable expansion: unballanced '['!");
						if (f!=(fend-1))
							throw jam_exception("Malformed variable expansion: unexpected ')'!");
						assert(collecting_string);

						//We've already collected a modifier
						process_mods(cur_mods,tmp);						
					} else
					{
						if (!collecting_string)
							throw jam_exception("Malformed variable expansion expression!");
						cur_mods+=iter[f].entry;
					}
				}
				else
				{
					assert(collecting_string);
					cur_mods+=(iter[f].pos)->c_str();
				}
				cur_var_name_valid_to=f;
			}
		}

		//Get the next value ('rotate' the 'iter' list like a mile counter in a car)
		bool got_value=false;
		for(size_t f=pieces.size();f>0 && !got_value;f--)
		{
			if (!iter[f-1].is_sublist_) continue;
			iter[f-1].pos++;
			if (iter[f-1].pos==iter[f-1].end)
				iter[f-1].pos=iter[f-1].begin;
			else
			{
				got_value=true;
				cur_var_name_valid_to=f-1;
				cur_var_name.resize(piece_pos_list[f-1]);
			}
		}		
		if (!got_value) break;
	};	
}



//Create a Cartesian product of two lists and place the result in the first list.
//For example, if 'first' is ['a-','b-','c-'], 'second' is ['1','2','3']
//then the result is:
//['a-1','a-2','a-3','b-1','b-2','b-3','c-1','c-2','c-3].
//Both lists must be non-null.
void cartesian_product(jam_list &first_and_res,const jam_list &second)
{
	assert(!first_and_res.empty() && !second.empty());

	if (second.size_is_one())
	{
		const jam_string &the_element=second.front();
		for(jam_list::iterator f=first_and_res.nc_begin(),fend=first_and_res.nc_end();f!=fend;++f)		
				*f+=the_element;
	} else
	{
		jam_list tmp=first_and_res;
		first_and_res.clear();
	
		for(jam_list::const_iterator f=tmp.begin(),fend=tmp.end();f!=fend;++f)
			for(jam_list::const_iterator n=second.begin(),nend=second.end();n!=nend;++n)
				first_and_res.push_back(*f+*n);
	}	
}



//Scan quoted string 
jam_string::const_iterator scan_quote(jam_string::const_iterator begin,
	jam_string::const_iterator end)
{
	assert(*begin=='"');

	bool inquote=true;
	jam_string::const_iterator pos=begin+1;
	while(pos!=end && inquote)
	{
		char c=*pos;
		if(c == '"')
			inquote = !inquote; //End of quote (")
		else if(c=='\\') //This is a screened character
		{
			//\c - screened character
			pos++; //Skip one more character
			if (pos==end)
				break; //This will throw exception in the check after the loop.
		}
		pos++;
	}
	if (pos==end)
		throw jam_exception("Malformed quoting in: '"+jam_string(begin,end)+"'!");

	return pos;
}



//Scan range for a variable
jam_string::const_iterator scan_for_var(jam_string::const_iterator begin,
	jam_string::const_iterator end)
{
	jam_string::const_iterator exp_begin;
	for(exp_begin=begin;exp_begin<end;++exp_begin)
	{
		char ch=*exp_begin;
		if(ch=='"')
			//Retrace the last step ('-1' part) because it must be scanned during
			//the next iteration.
			exp_begin=scan_quote(exp_begin,end)-1;
		else if(ch == '$' && (exp_begin+1)<end && *(exp_begin+1) == '(')
			break;
	}
	return exp_begin;
}



jam_string::const_iterator expand_string(const list_of_lists &func_args,
	const jam_module &context,
	jam_string::const_iterator pos_begin,
	jam_string::const_iterator pos_end, jam_list &res, 
	int level)
{
	assert(pos_begin!=pos_end);
	//res.reset();

	//Check if we can fast-track to direct copy
	jam_string::const_iterator exp_begin=scan_for_var(pos_begin,pos_end);

	if (exp_begin==pos_end)
	{
		assert(level!=0);
		//Create a list with return result if we're only in plain text.
		//We return the reference to the arguments, and this is only valid
		//on non-zero level
		res=jam_string(boost::cref(&*pos_begin),pos_end-pos_begin);
		return pos_end;
	}
	
	//Note: exp_being is now set on '$' symbol.
	jam_string::const_iterator pos=exp_begin;
	
	//This list accumulates pieces of variable names (there can be more than one
	//of them due to $($(var)) expansions.
	piece_list_t pieces;

	//This variable as an accumulator holding the current string value.
	//It is commited to the 'pieces' list when we encounter a ')' or a '$' token
	const char *cur_piece_begin=&*pos;
	//This variable contains the number of the last piece which contains
	//name. The next piece is a special symbol or the closing ')' brace.
	size_t last_name_piece=0;

	pos++; assert(pos<=pos_end);
	//Now 'pos' is on the opening brace of the variable

	bool found_end=false;
	while(!found_end)
	{
		if (pos==pos_end) throw jam_exception("Malformed variable name: '"+
			jam_string(pos_begin,pos_end)+"'!");
		
		char cur_ch=*pos;

		if (cur_ch=='$') //Oh no! It's an embedded variable!
		{
			if ((pos+1)==pos_end || *(pos+1)!='(')
				throw jam_exception("Malformed variable name: '"+
					jam_string(pos_begin,pos_end)+"'!");

			if (cur_piece_begin!=pos) //Commit accumulated value
				pieces.push_back(var_piece(jam_string(
				boost::cref(cur_piece_begin),pos-cur_piece_begin),false));

			//Create a new variable piece which will receive expanded values
			pieces.push_back(var_piece());
			var_piece &cur_list=pieces.back();

			//Expand the variable recursively.
			pos=expand_string(func_args,context, pos,pos_end,cur_list.val_list_,level+1);

			if (cur_list.val_list_.empty()) //Empty array is returned. Stop expansion and return the empty list
				return pos_end;

			//'pos' is now at the next element after the closing brace of embedded variable.
			//Update the piece position
			cur_piece_begin=pos;
			continue; //Continue scanning, but perform checks at the start of the loop
		} 
		
		++pos; //Continue scanning or consume the final brace

		if (cur_ch==')') //We've found the end of the current variable.
		{			
			//Commit accumulated value if any
			pieces.push_back(var_piece(jam_string(boost::cref(cur_piece_begin),
				pos-cur_piece_begin-1),false));
			//Closing brace gets its very own token
			pieces.push_back(var_piece(jam_string(boost::cref(")"),1),true));
			cur_piece_begin=pos;
			found_end=true;
		} else 
			//Special symbols get their own pieces
			if (cur_ch==':' || cur_ch=='[' || cur_ch==']') 
		{
			//Commit accumulated value if any
			if (cur_piece_begin!=(pos-1)) pieces.push_back(var_piece(
				jam_string(boost::cref(cur_piece_begin),pos-cur_piece_begin-1),false));

			if (pieces.size()==0) throw jam_exception("Modifier at the start of a variable: '"+
				jam_string(pos_begin,pos_end)+"'!");

			if (last_name_piece==0)
				last_name_piece=pieces.size();

			//Special symbol needs a separate piece
			pieces.push_back(var_piece(jam_string(1,cur_ch),true));

			cur_piece_begin=pos; //The next piece begins from the next character
		}		
	}
	assert(pos==cur_piece_begin);

	expand_var(func_args,context,pieces,last_name_piece,res);

	if (res.empty())
		return pos_end; //Empty array is returned. Stop expansion and return the empty list

	//Scan for postfix expansion
	jam_string str_postfix;
	if (level==0) //Only do postfix scanning if we're on the top level.
	{
		jam_string::const_iterator postfix_begin=scan_for_var(pos,pos_end);	
		str_postfix=jam_string(boost::cref(&*pos),postfix_begin-pos);
		pos=postfix_begin;
	}
	jam_string prefix(boost::cref(&*pos_begin),exp_begin-pos_begin);

	//Add prefix and postfix to the result list
	if (!prefix.empty())
		if (str_postfix.empty())
			for(jam_list::iterator f=res.nc_begin(),fend=res.nc_end();f!=fend;++f)
				*f=prefix+*f;
		else
			for(jam_list::iterator f=res.nc_begin(),fend=res.nc_end();f!=fend;++f)		
				*f=prefix+*f+str_postfix;
	else if (!str_postfix.empty())
		for(jam_list::iterator f=res.nc_begin(),fend=res.nc_end();f!=fend;++f)		
			*f+=str_postfix;

	//If there's a stuff left to parse - recurse into it WITHOUT increasing level and
	//do it ONLY if we're on the level zero.
	//This effectively emulates iteration.
	if (pos!=pos_end && level==0)
	{
		jam_list postfix;
		pos=expand_string(func_args,context,pos,pos_end,postfix,level);
		assert(pos==pos_end); //It should have consumed the rest of string
		if (postfix.empty())
		{
			res=null_list;
			return pos_end; //Empty array is returned. Stop expansion and return the empty list
		}
		cartesian_product(res,postfix);
	}

	return pos;
}



//Sidenote: we're using a jam_string here without any performance loss because
//it supports 'reference_semantics', but it can lead to errors because string
//may not be null-terminated.
//Also, jam_strings are refcounted so we can return them efficiently.
void expand_string(const list_of_lists &func_args,
	const jam_module &context, const jam_string &str, jam_list &res,
	int level)
{
	size_t bits=str.get_cache_mask();
	if (bits & TRIVIAL_STRING_BIT)
	{
		res.push_back(str);
		return;
	}

	if (!(bits & NON_TRIVIAL_STRING_BIT))
	{
		//Check if we can fast-track to direct copy
		jam_string::const_iterator exp_begin=scan_for_var(str.begin(),str.end());

		//Create a list with return result if there's nothing to expand.
		if (exp_begin==str.end())
		{
			res.push_back(str);
			str.set_cache_mask(bits | TRIVIAL_STRING_BIT);
			return;
		} else
			str.set_cache_mask(bits | NON_TRIVIAL_STRING_BIT);
	}

	//Well, we do need to expand variables creating a Cartesian product
	//of their values.	
	jam_string::const_iterator pos=expand_string(func_args,context,
		str.begin(),str.end(),res,level);
	assert(pos==str.end());	
}
